#lang sicp

;练习1.11
;递归计算
(define (f1.11-rec n)
  (cond ((< n 3) n)
        (else (+ (f1.11-rec (- n 1))
                 (* 2 (f1.11-rec (- n 2)))
                 (* 3 (f1.11-rec (- n 3)))))))
;迭代计算
(define (f1.11-iter n)
  (f1.11-iter_iter 2 1 0 n))
(define (f1.11-iter_iter a b c n)
  (if (< n 3)
      a
      (f1.11-iter_iter (+ a
                          (* 2 b)
                          (* 3 c))
                       a
                       b
                       (- n 1))))
;(f1.11-rec 5)
;(f1.11-iter 5000)

;------------------------------------------------
;练习1.12
;帕斯卡三角形

;获取n行
(define (f1.12 n)
  (cond ((= n 1) (f1.12.single 1))
        (else (cons (f1.12.single n)
                    (f1.12 (- n 1))))))
;获取第n行
(define (f1.12.single n)
  (cond ((= n 1) (list 1))
        (else (cons 1
                    (f1.12.1 (lastLsN (f1.12.single (- n 1))
                                      (- n 1))
                             (- n 1))))))
;获取列表ls的倒数n个值
(define (lastLsN ls n)
  (cond ((= (len ls) n) ls)
        (else (lastLsN (cdr ls)
                       n))))
;获取列表ls的长度
(define (len ls)
  (cond ((null? ls) 0)
        (else (+ 1
                 (len (cdr ls))))))
;自迭代获取杨辉三角形
(define (f1.12.iter n)
  (cond ((= n 1) (list 1))
        ((= n 2) (list (list 1 1)
                       (f1.12.iter 1)))
        (else (cons (cons 1
                          (f1.12.1 (car (f1.12.iter (- n 1)))
                                   (- n 1)))
                    (f1.12.iter (- n 1))))))

;获取列表ls每两个相邻值的和构造的列表，且在左右两侧分别添加值1
(define (f1.12.1 ls n)
  (cond ((= n 1) (list 1))
        (else (cons (+ (car ls)
                       (car (cdr ls)))
                    (f1.12.1 (cdr ls)
                             (- n 1))))))

;(f1.12 50)
;(f1.12.iter 5)

;---------------------------------------------------
;练习1.29
;辛普森数值积分

;递归计算式求和
(define (sum term a next b i)
  (if (> a b)
      0
      (+ (* (term a)
            (cond ((or (= a b) (= i 0)) 1)
                  ((= (modulo i 2) 0) 2)
                  (else 4)))
         (sum term (next a) next b (+ i 1)))))
;1.29
(define (f1.29 f a b n)
  (define (add-h x) (+ x (/ (- b a) n)))
  (* (/ (- b a) n)
     (/ 1 3)
     (sum f a add-h b 0)))

;立方函数
(define (cube x)
  (* x x x))

;(f1.29 cube 0 1 100)

;-------------------------------------------------
;练习1.30
;迭代计算式求和
(define (sum-iter term a next b)
  (define (iter a result i)
    (if (> a b)
        result
        (iter (next a)
              (+ result
                 (* (term a)
                    (cond ((or (= a b) (= i 0)) 1)
                          ((= (modulo i 2) 0) 2)
                          (else 4))))
              (+ i 1))))
  (iter a 0 0))

;1.30
(define (f1.30 f a b n)
  (define (add-h x) (+ x (/ (- b a) n)))
  (* (/ (- b a) n)
     (/ 1 3)
     (sum-iter f a add-h b)))

;(f1.30 cube 0 1 100)

;-----------------------------------------------------
;练习1.31
;累乘

;1.31-a
;递归计算式
(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))
(define (factorial n)
  (define (next x) (+ x 1))
  (define (term x) x)
  (product term 1 next n))

;(factorial 5)

(define (pi-appro n)
  (define (next x) (+ x 1))
  (define (term x)
    (cond ((= (modulo x 2) 1) (/ (+ x 1) (+ x 2)))
          (else (/ (+ x 2) (+ x 1)))))
  (product term 1 next n))


;(pi-appro 3)

;1.31-b
;迭代计算式
(define (product-iter term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a)
              (* (term a) result))))
  (iter a 1))

(define (pi-appro-iter n)
  (define (next x) (+ x 1))
  (define (term y)
    (cond ((= (modulo y 2) 1) (/ (+ y 1) (+ y 2)))
          (else (/ (+ y 2) (+ y 1)))))
  (product-iter term 1 next n))

;(pi-appro-iter 3)

;-----------------------------------------------------------
;练习1.32
;累积

;1.32-a
;递归计算式
(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate combiner null-value term (next a) b))))
;累加
(define (accumulate-sum term a next b)
  (define (sum x y) (+ x y))
  (accumulate sum 0 term a next b))
;累乘
(define (accumulate-product term a next b)
  (define (product x y) (* x y))
  (accumulate product 1 term a next b))

;1.32-b
;迭代计算式
(define (accumulate-iter combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a)
              (combiner (term a)
                        result))))
  (iter a null-value))
;累加
(define (accumulate-sum-iter term a next b)
  (define (sum x y) (+ x y))
  (accumulate-iter sum 0 term a next b))
;累乘
(define (accumulate-product-iter term a next b)
  (define (product x y) (* x y))
  (accumulate-iter product 1 term a next b))

;--------------------------------------------------------------
;练习1.33
;过滤器

(define (filtered-accumulate-v1 filter combiner null-value term a next b)
  (if (> a b)
      null-value
      (if (filter (term a))
          (combiner (term a)
                    (filtered-accumulate-v1 filter
                                         combiner
                                         null-value
                                         term
                                         (next a)
                                         next
                                         b))
          (filtered-accumulate-v1 filter
                               combiner
                               null-value
                               term
                               (next a)
                               next
                               b))))

(define (filtered-accumulate-v2 filter combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (if (filter (term a))
                    (term a)
                    null-value)
                (filtered-accumulate-v2 filter
                                        combiner
                                        null-value
                                        term
                                        (next a)
                                        next
                                        b))))

(define (acc-odd n)
  (define (term x) x)
  (define (next y) (+ y 1))
  (define (filter z) (= (modulo z 2) 1))
  (define (combiner u v) (+ u v))
  (filtered-accumulate-v2 filter combiner 0 term 1 next n))

;(acc-odd 9000)

;1.33-a
(define (sum-prime a b)
  (define (term x) x)
  (define (next y) (+ y 1))
  (define (prime z) (#t))
  (define (combiner u v) (+ u v))
  (filtered-accumulate-v2 prime
                          combiner
                          0
                          term
                          a
                          next
                          b))
;1.33-b
(define (product-gcd n)
  (define (term x) x)
  (define (next y) (+ y 1))
  (define (filter z) (= (gcd z n) 1))
  (define (combiner u v) (* u v))
  (filtered-accumulate-v2 filter
                          combiner
                          0
                          term
                          1
                          next
                          n))

;----------------------------------------------------
;练习1.35
;不动点 黄金分割率 x->1+1/x
(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

;(fixed-point cos 1.0)
;(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)

;----------------------------------------------------
;练习1.36
(define (fixed-point-display f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (display next)
      (newline)
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (average x y)
  (* 0.5
     (+ x y)))

;(fixed-point-display (lambda (x) (/ (log 1000) (log x))) 5)
;(newline)
;(fixed-point-display (lambda (x) (average x (/ (log 1000) (log x)))) 5)

;------------------------------------------------------------
;练习1.37
;无穷连分式 黄金分割率

;1.37-a
;递归计算式
(define (cont-frac n d k)
  (define (rec i)
    (if (= i k)
        1
        (/ (n i)
           (+ (d i)
              (rec (+ i 1))))))
  (rec 1))

;(cont-frac (lambda (i) 1.0)
;           (lambda (i) 1.)
;           50)

;1.37-b
;迭代计算式
(define (cont-frac-iter n d k)
  (define (iter result i)
    (if (= i 0)
        result
        (iter (/ (n i)
                 (+ (d i) result))
              (- i 1))))
  (iter (n k) k))

;(cont-frac-iter (lambda (i) 1.0)
;           (lambda (i) 1.0)
;           50)

;----------------------------------------------------------
;练习1.38
;e-2连分式，e的近似值

(define (f1.38_d i)
  (cond ((= i 1) 1)
        ((= i 2) 2)
        (else (let ((i_v (- i 2)))
                (if (= (modulo i_v 3) 0)
                    2
                    1)))))
(define (f1.38_e-2 n)
  (cont-frac-iter (lambda (i) 1.0)
                  f1.38_d
                  n))
;(f1.38_e-2 10)

;-----------------------------------------------------
;练习1.39
;正切函数连分式

(define (f1.39_d i) (- (* i 2) 1))
(define (tan-cf x k)
  (define (n i)
    (cond ((= i 1) x)
          (else (* -1 x x))))
  (cont-frac-iter n
                  f1.39_d
                  k))
(define PI 3.1415926)
;(tan-cf (/ PI 6) 50)

;----------------------------------------------------
;求某个函数的导数，返回另一个函数
(define dx 0.00001)
(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))
;牛顿法
(define (newton-transform g)
  (lambda (x)
    (- x
       (/ (g x)
          ((deriv g) x)))))

(define (newton-method g guess)
  (fixed-point (newton-transform g) guess))
(define (square x) (* x x))
(define (sqrt x)
  (newton-method (lambda (y) (- (square y) x))
                 1.0))

;-------------------------------------------
;练习1.40
(define (f1.40 a b c)
  (define (cubic a b c)
    (lambda (x)
      (+ (* x x x)
         (* a
            (* x
               x))
         (* b
            x)
         c)))
  (newton-method (cubic a b c)
                 1))
;(f1.40 0 0 1)

;---------------------------------------------
;练习1.41
;某过程的连续两次应用
(define (double f)
  (lambda (v)
    (f (f v))))
(define (inc i) (+ i 1))

;((double inc) 0)
;(((double double) inc) 0)
;(((double (double double)) inc) 0)

;--------------------------------------------------
;练习1.42
;复合函数
(define (compose f g)
  (lambda (x)
    (f (g x))))
;((compose square inc) 6)

;---------------------------------------------------
;练习1.43
;重复应用某函数n次

;递归计算式
(define (repeated f n)
  (lambda (x)
    (if (= n 1)
        (f x)
        ((compose f
                  (repeated f (- n 1)))
         x))))
;迭代计算式
(define (repeated-iter f n)
  (define (iter next_v i)
    (if (= i n)
        (f next_v)
        (iter (f next_v) (+ i 1))))
  (lambda (x)
    (iter x 1)))

;((repeated inc 15000) 0)
;((repeated square 2) 5)

;-----------------------------------------------
;练习1.44
;平滑某个函数
(define (smooth f)
  (lambda (x)
    (* (/ 1 3)
       (+ (f (- x dx))
          (f x)
          (f (+ x dx))))))
(define (smooth-repeated-n f n)
  ((repeated smooth n) f))

;((smooth inc) 2)
;((smooth-repeated-n inc 2) 2)

;-----------------------------------------------
;练习1.45
;计算n次方根
(define (average-damp f)
  (lambda (x) (average x (f x))))

;求x的n次方
(define (x^n x n)
  (define (term a) x)
  (define (next y) (+ y 1))
  (product-iter term 1 next n))

(define (f1.45 x n)
  (fixed-point (repeated (average-damp (lambda (y)
                                         (/ x
                                            (x^n y
                                                 (- n 1)))))
                         4)
               1.0))
;(x^n 2 2)
;(f1.45 2 4)

;--------------------------------------------------------------
;练习1.46
;迭代式改进的数值算法的抽象
(define (iterative-improve enough_good? improve_next)
  (define (rec guess)
    (if (enough_good? guess)
        guess
        (rec (improve_next guess))))
  (lambda (y)
    (rec y)))

(define (f1.46-fixed-point f first-guess)
  (define (enough_good? x)
      (< (abs (- x (f x))) tolerance))
  ((iterative-improve enough_good? f) first-guess))

;(f1.46-fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)